package main

//link: https://leetcode-cn.com/problems/target-sum/
func main() {

}

//动态规划表达式  dp[i][j]表示前i个数字中，和为j的方案数
// dp[i][j]=dp[i-1][j] //当j<nums[i]时;
// dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]]
func findTargetSumWays(nums []int, target int) int {
	sum := 0
	dp := make([][]int, len(nums)+1)
	for i := 0; i < len(nums); i++ {
		sum += nums[i]
	}
	diff := sum - target
	if diff < 0 || diff%2 == 1 {
		return 0
	}
	n, neg := len(nums), diff/2
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, neg+1)
	}
	dp[0][0] = 1
	for i, num := range nums {
		for j := 0; j <= neg; j++ {
			dp[i+1][j] = dp[i][j]
			if j >= num {
				dp[i+1][j] += dp[i][j-num]
			}
		}
	}
	return dp[n][neg]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
